Autor obrázku: Chris Martin http://en.wikipedia.org/wiki/User:Booyabazooka

Kombinatorické myšlení

Kombinatorika trochu jinak

Permutace s opakováním

diskuze, ke stažení v PDF: zadání

Úloha č. 1

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Následující úloha se skládá z několika podúloh. Rozdělte podúlohy do několika skupin (může to být i jen jediná skupina) tak, že všechny podúlohy v jedné skupině mají stejný výsledek. Výsledek podúloh v rámci skupiny není nutné určit a není podstatný. Hledejte důvody pro svá rozhodnutí. Skrýt.

Která z ostatních úloh vás vede k výpočtu ${n-1 \choose k-1} + {n-1 \choose k}?$
Program vybírá lidi z $n$ -členné skupiny. Kolika způsoby může výběr skončit?

$n$ -členné skupiny vybrat

$k$ reprezentantů?

(d) Která z ostatních úloh vás vede k výpočtu ${n \choose k}?$

Výsledek: (skrýt)

(a) = (b) = (c) = (d)

Výsledek

Řešení: (skrýt)

Pokud se program vydá horní větví (padne panna), zbývá mu vybrat $k-1$ ze zbývajících $n-1$ lidí. Pokud se vydá dolní větví (padne orel), zbývá mu vybrat všech $k$ ze zbývajících $n-1$ lidí (nejvyšší člověk už byl vyřazen). Možnosti obdržené horní větví jsou vždy odlišné od možností obdržených dolní větší, protože možnosti obdržené horní větví vždy obsahují nejvyššího člověka. Zato možnosti obdržené dolní větví nikdy neobsahují nejvyššího člověka. Horní větev může skončit ${n-1 \choose k-1}$ způsoby a dolní větev může skončit ${n-1 \choose k}$ způsoby. To celkem dává ${n-1 \choose k-1} + {n-1 \choose k}$ možností.
Přestože program v prvním kroku hodí mincí, stejně nakonec vybere $k$ lidí z $n$ -členné skupiny. Naopak i každý výběr $k$ lidí z $n$ -členné skupiny buď obsahuje, nebo neobsahuje nejvyššího člověka, a program jej tak může realizovat ve své horní, nebo dolní větvi.
Z dřívějška už víme, že výběr $k$ -členné skupiny z $n$ lidí lze provést ${n \choose k}$ způsoby.

Řešení

Úloha č. 2

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Která z ostatních úloh vás vede k výpočtu ${6 \choose 0}+{6 \choose 1}+{6 \choose 2}+{6 \choose 3}+{6 \choose 4}+{6 \choose 5}+{6 \choose 6}?$

(b) Kolik cest vede z nejsevernějšího města do nejjižnějšího?

$\searrow$ a

$\swarrow$ ? (Např.

$\swarrow\ \swarrow\ \searrow\ \searrow\ \searrow\ \swarrow$ nebo

$\searrow\ \searrow\ \searrow\ \searrow\ \searrow\ \swarrow$ )

(d) Kolika způsoby lze rozdělit šest lidí na dvě skupiny (jedna skupina může být i prázdná)?

(e) Kolika způsoby lze vybrat libovolně velkou skupinu (může být i prázdná) ze šesti lidí?

(f) Která z ostatních úloh vás vede k výpočtu

$2^6$ ?

Výsledek: (skrýt)

(a) = (b) = (c) = (e) = (f)

Výsledek

Řešení: (skrýt)

Počet cest vedoucích do nejjižnějšího města je součtem počtů cest vedoucích do měst v 7. řádku. Do nejzápadnějšího města v 7. řádku se přitom dá dostat ${6 \choose 0}$ způsoby, do druhého nejzápadnějšího ${6 \choose 1}$ způsoby, atd. až do nejvýchodnějšího města se dá dostat ${6 \choose 6}$ způsoby.
Každou cestu můžeme zapsat pomocí šesti šipek ( $\searrow$ nebo $\searrow$ ), podle toho, kterým směrem se cesta ubírá. Poslední krok cesty vždy směřuje do nejjižnějšího města.
Například dvojčlennou skupinu lze vybrat ${6 \choose 2}$ způsoby, trojčlennou skupinu lze vybrat ${6 \choose 3}$ způsoby, atd. Možnosti můžeme rozlišit podle velikosti skupiny a celkem pak dostaneme ${6 \choose 0}+{6 \choose 1}+{6 \choose 2}+{6 \choose 3}+{6 \choose 4}+{6 \choose 5}+{6 \choose 6}$ způsobů, jak vybrat libovolně velkou skupinu.
Volíme šest symbolů a pro každý z nich máme dvě možnosti ( $\searrow$ nebo $\searrow$ ), což dává $2\cdot2\cdot2\cdot2\cdot2\cdot2 = 2^6$ různých nápisů. Můžeme propojit například i podúlohy (e) a (f) – u každého člověka se rozhodneme, zda jej do skupiny zařadíme, nebo nezařadíme.
Tato úloha je odlišná. Na první pohled se může zdát stejná jako úloha (e), ale není tomu tak. Abychom to nahlédli, nejdříve si lidi očíslujme čísly $1$ až $6$ . V podúloze (e) je jeden z výběrů například $\{1,2,4,6\}$ . Jiný z výběrů je $\{3,5\}$ . Oba tyto výběry ale v podúloze (d) znamenají rozdělí na dvě stejné skupiny. To znamená, že počet způsobů v podúloze (d) je menší než počet způsobů v podúloze (e).

Řešení

Úloha č. 3

Na obrázku jsou výsledky běhu na 100 m mužů z Olympijských her v Londýně z roku 2012.

(a) Kolika způsoby mohl závod skončit? (Dva závody považujeme za různé, pokud se liší alespoň na jedné pozici.)
(b) Ke každému pořadí vlajek lze dopsat několik pořadí jmen závodníků. Kolik?
(c) Zjistěte, kolik je všech pořadí vlajek.

Výsledek: (skrýt)

(a): $8! = 40320$ , (b): $3!\cdot3!=36$ , (c): $8! / (3!\cdot3!) = 1120$ .

Výsledek

Řešení: (skrýt)

Postupným výběrem běžců na první, druhou, třetí, atd. až osmou pozici dojdeme k výsledku $8\cdot 7 \cdot 6 \dots 1 = 8! = 40320$ .
Můžeme zaměňovat jména u amerických vlajek. To lze provést $3\cdot2\cdot1=3!=6$ způsoby. Také lze zaměňovat jména u jamajských vlajek, což lze provést též $3!=6$ způsoby. Tyto záměny můžeme mezi sebou jakkoliv kombinovat, a to nám dává $6\cdot6=36$ pořadí závodníků, kterým odpovídá pořád totéž pořadí vlajek.
Z části (b) víme, že každé pořadí vlajek je $36$ krát započteno mezi pořadími závodníků. Pořadí vlajek je proto $36$ krát méně, což je $8!/36 = 1120$ .

Řešení

Úloha č. 4

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

V osudí jsou kuličky očíslované čísly $1$ až $16$ . $5$ kuliček je bílých, $5$ je modrých, $4$ zelené a $2$ jsou hnědé. Kuličky postupně po jedné vytáhneme a naskládáme je do řady v pořadí, v jakém byly taženy. Nakonec všechny kuličky otočíme číslem dolů tak, že je vidět pouze jejich barva. Kolik různě barevných řad tak můžeme dostat? Například lze dostat tyto dvě různé řady: $(H, M, H, M, M, M, B, M, B, B, Z, Z, Z, Z, B, B)$ , $(B, B, Z, Z, Z, Z, B, B, M, B, M, M, M, H, M, H)$ .
Na první trénink malých fotbalistů přišlo $16$ šestiletých kluků. Trenér se rozhodl, že $2$ z nich postaví do brány, $5$ z nich budou obránci, jiných $5$ budou záložníci a poslední $4$ útočníci. Kolika způsoby mohl kluky rozdělit?
Která z ostatních úloh vás vede k výpočtu $\frac{16!}{2!\,4!\,5!\,5!}?$
Která z ostatních úloh vás vede k výpočtu ${16 \choose 5}{11 \choose 5}{6 \choose 4}{2 \choose 2}?$

Výsledek: (skrýt)

(a) = (b) = (c) = (d)

Výsledek

Řešení: (skrýt)

Očíslované kuličky je možné seřadit $16!$ způsoby. Budeme brát kuličky pouze jedné barvy a otočíme je tak, že jejich čísla nebudou vidět. Stanou se tak nerozlišitelnými (analogie k závodníkům reprezentujícím stejnou zemi – z pohledu vlajek jsou závodníci stejné země nerozlišitelní).
Řekněme, že nejdříve si vybereme hnědé kuličky a že první hnědá kulička byla 14. a druhá 16. To nám ale dá stejně barevnou řadu jako kdyby první hnědá kulička byla 16. a druhá 14. (podobně jako záměna závodníků stejného státu nezmění pořadí vlajek). Počet těchto barevných řad (na všech kuličkách je vidět číslo, pouze na hnědých není) tak bude dvakrát menší.
Potom si vybereme zelené kuličky a otočíme je tak, že jejich čísla nebudou vidět. Tím se stanou nerozlišitelné všechny řady, v nichž byly navzájem proházené zelené kuličky. Zelené kuličky lze navzájem proházet $4!=24$ způsoby, takže počet nových barevných řad (modré a bílé kuličky jsou očíslovány, zelené a hnědé kuličky nejsou očíslovány) zase $4!$ -krát klesne. Tuto úvahu ještě dvakrát opakujeme pro modré a bílé kuličky. Dojdeme tak k výpočtu $\frac{16!}{2!\,4!\,5!\,5!}$ .
Ze skupiny $16$ fotbalistů nejdříve vybereme $5$ záložníků. To lze provést ${16 \choose 5}$ způsoby a zbyde nám $11$ fotbalistů. Ze zbývajících $11$ fotbalistů vybereme $5$ obránců, což lze provést ${11 \choose 5}$ způsoby. Zbyde nám $6$ fotbalistů a z nich vybereme $4$ útočníky, což lze provést ${6 \choose 4}$ způsoby. Zbývající dva fotbalisté se stanou brankáři. Jakýkoliv výběr $5$ záložníků lze libovolně kombinovat s výběrem $5$ obránců. Tyto výběry lze dále libovolně kombinovat s výběrem $4$ útočníků. To nás vede k výpočtu ${16 \choose 5}\cdot {11 \choose 5}\cdot {6 \choose 4}$ nebo též ${16 \choose 5}{11 \choose 5}{6 \choose 4}{2 \choose 2}$ .
Též bychom mohli fotbalisty seřadit do řady, každému z nich dát jednu z barevných kuliček (máme $5$ modrých, $5$ bílých, $4$ zelené a $2$ hnědé) a říct, že ti s modrou kuličkou budou záložníci, ti s bílou obránci, ti se zelenou útočníci a ti s hnědou brankáři.
Jiná možnost je ukázat, že výrazy $\frac{16!}{2!\,4!\,5!\,5!}$ a ${16 \choose 5}{11 \choose 5}{6 \choose 4}{2 \choose 2}$ jsou ve skutečnosti stejné (ač na první pohled nevypadají). To lze nahlédnout rozepsáním kombinačních čísel (např. ${16 \choose 4} = \frac{16!}{4!12!}$ ) a krácením zlomku.

Řešení

Úloha č. 5

Mezi městy na obrázku je naznačena letecká síť, v níž z každého města vede cesta do všech měst dále na východ.

(a) Pro každé město určete, kolika způsoby se do něj lze dopravit ze nejzápadnějšího města.
Jak se změní výsledek úlohy, pokud měst v řadě bude $n$ ?
(c) Ptáme-li se na počet možností, jak obarvit vnitřní města (tj. neležící na ani jednom kraji) modře či žlutě, dostaneme stejnou odpověď. Proč?

Výsledek: (skrýt)

Od západu na východ postupně $1, 1, 2, 4, 8, 16$ .
Do nejvýchodnějšího města vede $2^{n-2}$ cest.
(c) Viz řešení.

Výsledek

Řešení: (skrýt)

(a) Čísla vyplňujeme postupně ze západu na východ.
Řekněme, že už známe výsledky pro $6$ měst (část (a)) a přidáme sedmé město. Do něj se můžeme dostat buď přímou linkou z prvního města, nebo přímou linkou ze druhého města, atd. To nám dává $1+1+2+4+8+16 = 32$ způsobů, jak dojít do sedmého města. Obecně řekněme, že již známe výsledky pro $n-1$ měst a přidáme $n$ -té město. Do něj se lze dostat $1+1+2+4+\dots+2^{n-3}=2^{n-2}$ způsoby.
Část (b) můžeme řešit i jinak. Každou cestu ze západu na východ můžeme popsat tak, že řekneme, která města jsme přeskočili a která jsme navštívili. U každého vnitřního města se tedy rozhodujeme, zda jej přeskočit, nebo navštívit. Počet cest nám tak rovnou vyjde jako $2\cdot2\cdot2\dots2=2^{\textrm{počet vnitřních měst}}=2^{n-2}$ .

Řešení

Shrnutí: V úloze o běžcích a v úloze o barevných kuličkách se počítají takzvané permutace s opakováním. Řekněme, že máme k dispozici 16 objektů, z nichž 5 je jednoho druhu, dalších 5 jiného druhu, další 4 zase jiného druhu a poslední 2 ještě jiného druhu. Objekty v rámci jednoho druhu nelze odlišit. Počet způsobů, kterými lze těchto 16 objektů seřadit, je $\frac{16!}{5!5!4!2!}.$

Předchozí výsledek lze rozšířit pro $k$ druhů objektů. Máme-li 1. druhu $n_1$ objektů, 2. druhu $n_2$ objektů, atd., až posledního $k$ . druhu $n_k$ objektů, pak počet způsobů, kterými lze těchto $n_1+n_2+\ldots+n_k$ objektů seřadit, je $\frac{(n_1+n_2+\ldots+n_k)!}{n_1!n_2!\cdots n_k!}.$

Hodiny

Bonusy

Permutace s opakováním

Úloha č. 1

Úloha č. 2

Úloha č. 3

Úloha č. 4

Úloha č. 5